package indi.leetcode;

import java.util.Stack;

/**
 * 用栈实现队列
 */
public class Q_232 {

    /**
     * push时间复杂度O(n)
     */
    class MyQueue_1 {

        private Stack<Integer> s1;
        private Stack<Integer> s2;
        private int front;

        /** Initialize your data structure here. */
        public MyQueue_1() {
            s1 = new Stack<>();
            s2 = new Stack<>();
        }

        /** Push element x to the back of queue. */
        public void push(int x) {
            if(s1.isEmpty()) {
                front = x;
            }
            if (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
            s2.push(x);
            if(!s2.isEmpty()){
                s1.push(s2.pop());
            }

        }

        /** Removes the element from in front of queue and returns that element. */
        public int pop() {
            int res = s1.pop();
            if(!s1.isEmpty()){
                front = s1.peek();
            }
            return res;
        }

        /** Get the front element. */
        public int peek() {
            return front;
        }

        /** Returns whether the queue is empty. */
        public boolean empty() {
            return s1.size() == 0;
        }
    }



    class MyQueue_2 {

        private Stack<Integer> s1;
        private Stack<Integer> s2;
        private int front;

        /** Initialize your data structure here. */
        public MyQueue_2() {
            s1 = new Stack<>();
            s2 = new Stack<>();
        }

        /** Push element x to the back of queue. */
        public void push(int x) {
            if(s1.isEmpty()) {
                front = x;
            }
            s1.push(x);
        }

        /** Removes the element from in front of queue and returns that element. */
        public int pop() {
            if(s2.isEmpty()){
                while (!s1.isEmpty()){
                    s2.push(s1.pop());
                }
            }
            return s2.pop();
        }

        /** Get the front element. */
        public int peek() {
            if(!s2.isEmpty()){
                front = s2.peek();
            }
            return front;
        }

        /** Returns whether the queue is empty. */
        public boolean empty() {
            return s1.isEmpty() && s2.isEmpty();
        }
    }


}
